package summary;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/20 15:51
 */
public class Title22 {

    List<String> result = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs("", n, 0, 0);
        return result;
    }

    private void dfs(String s, int n, int lcur, int rcur) {
        if (lcur > n || rcur > n || rcur > lcur) {
            return;
        }
        if (lcur == n && rcur == n) {
            result.add(s);
            return;
        }
        dfs(s + "(", n, lcur + 1, rcur);
        dfs(s + ")", n, lcur, rcur + 1);
    }

    public static void main(String[] args) {

    }
}
